/*
 * Copyright 北京航空航天大学  @ 2015 版权所有
 */
package com.buaa.edu.leetcode.algorithm.twopoint;

/**
 * <p>三色排序.
 * 要求相同颜色在一起。红白蓝顺序，代表012，时间复杂度O(n)
 * M1:计数排序
 * M2：两指针
 * </p>
 * @author towan
 * @email tongwenzide@163.com
 * @time 2015年5月31日
 */
public class SortColors {
    
    public void sortColors(int[] nums) {
        //两个异向指针
        int first = 0;
        int second = nums.length;
        for(int i=0;i<second;i++){
            //0放首部
            if(nums[i]==0){
                int tmp = nums[first];
                nums[first] = nums[i];
                nums[i] = tmp;
                first++;
                
            }else if(nums[i]==2){
              //2放尾部
                second--;
                int tmp = nums[second];
                nums[second] = nums[i];
                nums[i] = tmp;
                i--;            }
        }
    }
}
